home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / CTOOLS10.ARJ / DLIST.C < prev    next >
C/C++ Source or Header  |  1992-02-15  |  12KB  |  391 lines
  1. /****************************************************************************
  2. *
  3. *                    Copyright (C) 1991 Kendall Bennett.
  4. *                            All rights reserved.
  5. *
  6. * Filename:        $RCSfile: dlist.c $
  7. * Version:        $Revision: 1.5 $
  8. *
  9. * Language:        ANSI C
  10. * Environment:    any
  11. *
  12. * Description:    Module to implement doubly linked lists. Includes a routine
  13. *                to peform a mergesort on the doubly linked list.
  14. *
  15. * $Id: dlist.c 1.5 91/12/31 19:39:49 kjb Exp $
  16. *
  17. * Revision History:
  18. * -----------------
  19. *
  20. * $Log:    dlist.c $
  21. * Revision 1.5  91/12/31  19:39:49  kjb
  22. * Modified include file directories.
  23. * 
  24. * Revision 1.4  91/10/28  03:16:39  kjb
  25. * Ported to the Iris.
  26. * 
  27. * Revision 1.3  91/09/27  03:09:18  kjb
  28. * Cosmetic change.
  29. * 
  30. * Revision 1.2  91/09/03  18:27:42  ROOT_DOS
  31. * Ported to UNIX.
  32. * 
  33. * Revision 1.1  91/09/01  18:35:23  ROOT_DOS
  34. * Initial revision
  35. * 
  36. ****************************************************************************/
  37.  
  38. #include <stdio.h>
  39. #include <malloc.h>
  40. #include <signal.h>
  41. #include "debug.h"
  42. #include "dlist.h"
  43.  
  44. PUBLIC void *dlst_newnode(int size)
  45. /****************************************************************************
  46. *
  47. * Function:        dlst_newnode
  48. * Parameters:    size    - Amount of memory to allocate for node
  49. * Returns:      Pointer to the allocated node's user space.
  50. *
  51. * Description:    Allocates the memory required for a node, adding a small
  52. *                header at the start of the node. We return a reference to
  53. *                the user space of the node, as if it had been allocated via
  54. *                malloc().
  55. *
  56. ****************************************************************************/
  57. {
  58.     DLST_BUCKET    *node;
  59.  
  60.     if ( !(node = (DLST_BUCKET*)malloc(size + sizeof(DLST_BUCKET))) ) {
  61.         fprintf(stderr,"Not enough memory to allocate list node.\n");
  62.         raise(SIGABRT);
  63.         return NULL;
  64.         }
  65.  
  66.     return DLST_USERSPACE(node);        /* Return pointer to user space */
  67. }
  68.  
  69. PUBLIC void dlst_freenode(void *node)
  70. /****************************************************************************
  71. *
  72. * Function:        dlst_freenode
  73. * Parameters:    node    - Node to free.
  74. *
  75. * Description:  Frees a node previously allocated with lst_newnode().
  76. *
  77. ****************************************************************************/
  78. {
  79.     free(DLST_HEADER(node));
  80. }
  81.  
  82. PUBLIC DLIST *dlst_init(void)
  83. /****************************************************************************
  84. *
  85. * Function:        dlst_init
  86. * Returns:      Pointer to a newly created list.
  87. *
  88. * Description:    Initialises a list and returns a pointer to it.
  89. *
  90. ****************************************************************************/
  91. {
  92.     DLIST    *l;
  93.  
  94.     if ((l = (DLIST*)malloc(sizeof(DLIST))) != NULL) {
  95.         l->count = 0;
  96.         l->head = &(l->hz[0]);
  97.         l->z = &(l->hz[1]);
  98.         l->head->next = l->z->next = l->z;
  99.         l->z->prev = l->head->prev = l->head;
  100.         }
  101.     else {
  102.         fprintf(stderr,"Insufficient memory to allocate list\n");
  103.         raise(SIGABRT);
  104.         return NULL;
  105.         }
  106.  
  107.     return l;
  108. }
  109.  
  110. PUBLIC void dlst_kill(DLIST *l,void (*freeNode)(void *node))
  111. /****************************************************************************
  112. *
  113. * Function:        dlst_kill
  114. * Parameters:    l            - List to kill
  115. *                freeNode    - Pointer to user routine to free a node
  116. *
  117. * Description:    Kills the list l, by deleting all of the elements contained
  118. *                within the list one by one and then deleting the list
  119. *                itself. Note that we call the user supplied routine
  120. *                (*freeNode)() to free each list node. This allows the user
  121. *                program to perform any extra processing needed to kill each
  122. *                node (if each node contains pointers to other items on the
  123. *                heap for example). If no extra processing is required, just
  124. *                pass the address of dlst_freenode(), ie:
  125. *
  126. *                    dlst_kill(myList,dlst_freenode);
  127. *
  128. ****************************************************************************/
  129. {
  130.     DLST_BUCKET    *n,*p;
  131.  
  132.     n = l->head->next;
  133.     while (n != l->z) {            /* Free all nodes in list                */
  134.         p = n;
  135.         n = n->next;
  136.         (*freeNode)(DLST_USERSPACE(p));
  137.         }
  138.     free(l);                    /* Free the list itself                    */
  139. }
  140.  
  141. PUBLIC void dlst_insertafter(DLIST *l,void *node,void *after)
  142. /****************************************************************************
  143. *
  144. * Function:        lst_insertafter
  145. * Parameters:    l        - List to insert node into
  146. *                node    - Pointer to user space of node to insert
  147. *                after    - Pointer to user space of node to insert node after
  148. *
  149. * Description:    Inserts a new node into the list after the node 'after'. To
  150. *                insert a new node at the beginning of the list, user the
  151. *                macro DLST_HEAD in place of 'after'. ie:
  152. *
  153. *                    dlst_insertafter(mylist,node,DLST_HEAD(mylist));
  154. *
  155. ****************************************************************************/
  156. {
  157.     DLST_BUCKET    *n = DLST_HEADER(node),*a = DLST_HEADER(after);
  158.  
  159.     n->next = a->next;
  160.     a->next = n;
  161.     n->prev = a;
  162.     n->next->prev = n;
  163.     l->count++;
  164. }
  165.  
  166. PUBLIC void *dlst_deletenext(DLIST *l,void *node)
  167. /****************************************************************************
  168. *
  169. * Function:        lst_deletenext
  170. * Parameters:    l        - List to delete node from.
  171. *                node    - Node to delete the next node from
  172. * Returns:        Pointer to the deleted node's userspace.
  173. *
  174. * Description:    Removes the node AFTER 'node' from the list l.
  175. *
  176. ****************************************************************************/
  177. {
  178.     DLST_BUCKET    *n = DLST_HEADER(node);
  179.  
  180.     node = DLST_USERSPACE(n->next);
  181.     n->next->next->prev = n;
  182.     n->next = n->next->next;
  183.     l->count--;
  184.     return node;
  185. }
  186.  
  187. PUBLIC void *dlst_first(DLIST *l)
  188. /****************************************************************************
  189. *
  190. * Function:        dlst_first
  191. * Parameters:    l        - List to obtain first node from
  192. * Returns:        Pointer to first node in list, NULL if list is empty.
  193. *
  194. * Description:    Returns a pointer to the user space of the first node in
  195. *                the list. If the list is empty, we return NULL.
  196. *
  197. ****************************************************************************/
  198. {
  199.     DLST_BUCKET    *n;
  200.  
  201.     n = l->head->next;
  202.     return (n == l->z ? NULL : DLST_USERSPACE(n));
  203. }
  204.  
  205. PUBLIC void *dlst_last(DLIST *l)
  206. /****************************************************************************
  207. *
  208. * Function:        dlst_last
  209. * Parameters:    l    - List to obtain last node from
  210. * Returns:        Pointer to last node in list, NULL if list is empty.
  211. *
  212. * Description:    Returns a pointer to the user space of the last node in
  213. *                the list. If the list is empty, we return NULL.
  214. *
  215. ****************************************************************************/
  216. {
  217.     DLST_BUCKET    *n;
  218.  
  219.     n = l->z->prev;
  220.     return (n == l->head ? NULL : DLST_USERSPACE(n));
  221. }
  222.  
  223. PUBLIC void *dlst_next(void *prev)
  224. /****************************************************************************
  225. *
  226. * Function:        dlst_next
  227. * Parameters:    prev    - Previous node in list to obtain next node from
  228. * Returns:        Pointer to the next node in the list, NULL at end of list.
  229. *
  230. * Description:    Returns a pointer to the user space of the next node in the
  231. *                list given a pointer to the user space of the previous node.
  232. *                If we have reached the end of the list, we return NULL. The
  233. *                end of the list is detected when the next pointer of a node
  234. *                points back to itself, as does the dummy last node's next
  235. *                pointer. This enables us to detect the end of the list
  236. *                without needed access to the list data structure itself.
  237. *
  238. *                NOTE:    We do no checking to ensure that 'prev' is NOT a
  239. *                        NULL pointer.
  240. *
  241. ****************************************************************************/
  242. {
  243.     DLST_BUCKET    *n = DLST_HEADER(prev);
  244.  
  245.     n = n->next;
  246.     return (n == n->next ? NULL : DLST_USERSPACE(n));
  247. }
  248.  
  249. PUBLIC void *dlst_prev(void *next)
  250. /****************************************************************************
  251. *
  252. * Function:        dlst_prev
  253. * Parameters:    next    - Next node in list to obtain previous node from
  254. * Returns:        Pointer to the previous node in the list, NULL at start list.
  255. *
  256. * Description:    Returns a pointer to the user space of the prev node in the
  257. *                list given a pointer to the user space of the next node.
  258. *                If we have reached the start of the list, we return NULL. The
  259. *                start of the list is detected when the prev pointer of a node
  260. *                points back to itself, as does the dummy head node's prev
  261. *                pointer. This enables us to detect the start of the list
  262. *                without needed access to the list data structure itself.
  263. *
  264. *                NOTE:    We do no checking to ensure that 'next' is NOT a
  265. *                        NULL pointer.
  266. *
  267. ****************************************************************************/
  268. {
  269.     DLST_BUCKET    *n = DLST_HEADER(next);
  270.  
  271.     n = n->prev;
  272.     return (n == n->prev ? NULL : DLST_USERSPACE(n));
  273. }
  274.  
  275. /* Static globals required by merge()    */
  276.  
  277. static DLST_BUCKET    *z;
  278. static int             (*cmp)(void*,void*);
  279.  
  280. PRIVATE DLST_BUCKET *merge(DLST_BUCKET *a,DLST_BUCKET *b,DLST_BUCKET **end)
  281. /****************************************************************************
  282. *
  283. * Function:        merge
  284. * Parameters:    a,b        - Sublist's to merge
  285. * Returns:        Pointer to the merged sublists.
  286. *
  287. * Description:    Merges two sorted lists of nodes together into a single
  288. *                sorted list.
  289. *
  290. ****************************************************************************/
  291. {
  292.     DLST_BUCKET    *c;
  293.  
  294.     /* Go through the lists, merging them together in sorted order    */
  295.  
  296.     c = z;
  297.     while (a != z && b != z) {
  298.         if ((*cmp)(DLST_USERSPACE(a),DLST_USERSPACE(b)) <= 0) {
  299.             c->next = a; c = a; a = a->next;
  300.             }
  301.         else {
  302.             c->next = b; c = b; b = b->next;
  303.             }
  304.         };
  305.  
  306.     /* If one of the lists is not exhausted, then re-attach it to the end
  307.      * of the newly merged list
  308.      */
  309.  
  310.     if (a != z) c->next = a;
  311.     if (b != z) c->next = b;
  312.  
  313.     /* Set *end to point to the end of the newly merged list    */
  314.  
  315.     while (c->next != z) c = c->next;
  316.     *end = c;
  317.  
  318.     /* Determine the start of the merged lists, and reset z to point to
  319.      * itself
  320.      */
  321.  
  322.     c = z->next; z->next = z;
  323.     return c;
  324. }
  325.  
  326. PUBLIC void dlst_mergesort(DLIST *l,int (*cmp_func)(void*,void*))
  327. /****************************************************************************
  328. *
  329. * Function:        dlst_mergesort
  330. * Parameters:    l            - List to merge sort
  331. *                cmp_func    - Function to compare two user spaces
  332. *
  333. * Description:    Mergesort's all the nodes in the list. 'cmp' must point to
  334. *                a comparison function that can compare the user spaces of
  335. *                two different nodes. 'cmp' should work the same as
  336. *                strcmp(), in terms of the values it returns. Rather than
  337. *                waste processing time keeping the previous pointers up to
  338. *                date while performing the mergesort, we simply run through
  339. *                the list at the end of the sort to fix the previous pointers.
  340. *
  341. ****************************************************************************/
  342. {
  343.     int            i,N;
  344.     DLST_BUCKET    *a,*b;        /* Pointers to sublists to merge            */
  345.     DLST_BUCKET    *c;            /* Pointer to end of sorted sublists        */
  346.     DLST_BUCKET    *head;        /* Pointer to dummy head node for list        */
  347.     DLST_BUCKET    *todo;        /* Pointer to sublists yet to be sorted        */
  348.     DLST_BUCKET    *t;            /* Temporary                                */
  349.  
  350.     /* Set up globals required by merge() and pointer to head    */
  351.  
  352.     z = l->z; cmp = cmp_func; head = l->head;
  353.  
  354.     for (N = 1,a = z; a != head->next; N = N + N) {
  355.         todo = head->next; c = head;
  356.         while (todo != z) {
  357.  
  358.             /* Build first sublist to be merged, and splice from main list
  359.              */
  360.  
  361.             a = t = todo;
  362.             for (i = 1; i < N; i++) t = t->next;
  363.             b = t->next; t->next = z; t = b;
  364.  
  365.             /* Build second sublist to be merged and splice from main list
  366.              */
  367.  
  368.             for (i = 1; i < N; i++) t = t->next;
  369.             todo = t->next; t->next = z;
  370.  
  371.             /* Merge the two sublists created, and set 'c' to point to the
  372.              * end of the newly merged sublists.
  373.              */
  374.  
  375.             c->next = merge(a,b,&t); c = t;
  376.             }
  377.         }
  378.  
  379.     /* Fix the previous pointers for the list    */
  380.  
  381.     a = b = l->head;
  382.     b = b->next;
  383.     while (1) {
  384.         b->prev = a;
  385.         if (b == z)
  386.             break;
  387.         a = a->next;
  388.         b = b->next;
  389.         }
  390. }
  391.